package 每日一题;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-03
 **/

public class No407接雨水II {

    /**
     * 给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，
     * 请计算图中形状最多能接多少体积的雨水。
     * <p>
     * 示例 1:
     * 输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
     * 输出: 4
     * 解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。
     * 示例 2:
     * 输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
     * 输出: 10
     *  
     * 提示:
     * m == heightMap.length
     * n == heightMap[i].length
     * 1 <= m, n <= 200
     * 0 <= heightMap[i][j] <= 2 * 104
     */

    /**
     * 思路: 农村包围城市,最小堆吃入边围的块,然后每次出列最小元素,每次都取出最小的元素,和周围的元素依次进行比较(没有path过的元素)
     * 如果目标元素比当前元素低,那么目标元素就可以注水(必定的,因为当前元素是周围的最小元素,那么目标元素一定可以注到和当前元素持平的水位)
     * 然后将目标元素放入堆中,且记目标元素的高max(注水后的高度,当前元素高度)。
     */

    private boolean[][] path;
    private int[][] around = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int trapRainWater(int[][] heightMap) {
        int allLength = heightMap.length;
        int itemLength = heightMap[0].length;
        this.path = new boolean[heightMap.length][heightMap[0].length];
        PriorityQueue<Pair> pairPriorityQueue = new PriorityQueue<>(Comparator.comparingInt(p -> p.num));

        // 上围放入
        for (int i = 0; i < this.path[0].length; i++) {
            this.path[0][i] = true;
            pairPriorityQueue.add(new Pair(0, i, heightMap[0][i]));
        }
        // 左围放入
        for (int i = 1; i < this.path.length; i++) {
            this.path[i][0] = true;
            pairPriorityQueue.add(new Pair(i, 0, heightMap[i][0]));
        }
        // 下围放入
        for (int i = 1; i < this.path[0].length; i++) {
            this.path[allLength - 1][i] = true;
            pairPriorityQueue.add(new Pair(allLength - 1, i, heightMap[allLength - 1][i]));
        }
        // 右围放入
        for (int i = 1; i < this.path.length - 1; i++) {
            this.path[i][itemLength - 1] = true;
            pairPriorityQueue.add(new Pair(i, itemLength - 1, heightMap[i][itemLength - 1]));
        }

        int result = 0;

        while (!pairPriorityQueue.isEmpty()) {
            // 获得最小的pair点,看其周围是否有比它小的&&没有走过的路径,获取它的差值
            Pair minPair = pairPriorityQueue.poll();
            System.out.println(minPair);
            for (int i = 0; i < 4; i++) {
                int nextX = minPair.x + this.around[i][0];
                int nextY = minPair.y + this.around[i][1];
                if (nextX >= 0 && nextX < allLength && nextY >= 0 && nextY < itemLength && !this.path[nextX][nextY]) {
                    // next元素低了,则周围这个元素可以注入水,因为它周围的元素肯定是高的
                    if (minPair.num > heightMap[nextX][nextY]) {
                        result += (minPair.num - heightMap[nextX][nextY]);
                    }
                    // 可能next元素低了
                    pairPriorityQueue.add(new Pair(nextX, nextY, Math.max(heightMap[nextX][nextY], minPair.num)));
                    this.path[nextX][nextY] = true;
                }
            }
        }

        return result;
    }

    static class Pair {
        public Pair(int x, int y, int num) {
            this.x = x;
            this.y = y;
            this.num = num;
        }

        private int x;
        private int y;
        private int num;

        @Override
        public String toString() {
            return this.x + "," + this.y + "=" + this.num;
        }
    }

    public static void main(String[] args) {
        No407接雨水II n = new No407接雨水II();
        int[][] arr = {{1, 4, 3, 1, 3, 2}, {3, 2, 1, 3, 2, 4}, {2, 3, 3, 2, 3, 1}};
        int result = n.trapRainWater(arr);
        System.out.println(result);

    }

}
